#include <stdio.h>
#include <stdlib.h>
#include <string.h>


/**
 * @brief 本程序将中缀表达式转换为后缀表达式。
 * 
 */
typedef char ElementType;

struct stack_node;

typedef struct {
    ElementType data;
    struct stack_node* next;
} stack_node, *pStackNode;

typedef struct 
{
    pStackNode top;
    pStackNode base;
    int size;
} stack, *pstack;

#define OK 1
#define ERROR 2

int InitStack(pstack p_stack)
{
    p_stack->top = p_stack->base = 0;
    p_stack->size = 0;
    return OK;
}

int Push(pstack stack, ElementType e)
{
    pStackNode node = (pStackNode) malloc(sizeof(stack_node));
    if (!node)
    {   
        printf("malloc error");
        return ERROR;
    }

    node->data = e;
    
    // 当栈为空的情况
    if (stack->base == 0) {
        stack->top = stack->base = node;
    } else 
    {
        // 栈不为空
        node->next = stack->top;
        stack->top = node;
    }
    stack->size++;
    return OK;
}

int Pop(pstack stack, ElementType *e)
{
    if (stack->base == 0)
    {
        printf("stack is empty\n");
        return ERROR;
    }
    pStackNode stack_top = stack->top;
    *e = stack_top->data;
    if (stack_top == stack->base)
    {
        stack->top = stack->base = 0;
    } else
    {
        stack->top = stack_top->next;
    }
    free(stack_top);
    stack->size--;
    return OK;
}

int StackSize(pstack stack)
{
    return stack->size;
}

int GetTop(pstack ps, ElementType *e)
{
    if (!ps->base)
    {
        return ERROR;
    }
    *e = ps->top->data;
    return OK;
}

int main(int argc, char* argv[])
{
    stack s;
    char* in = "1+2*4/(5-7)+3/6";
    char out[50];
    int i = 0;
    char* p = in;
    char top;
    int pop_result;
    InitStack(&s);
    while (*p)
    {
        switch (*p)
        {
        case '+':
        case '-':
            while (StackSize(&s) > 0)
            {
                GetTop(&s, &top);
                if (top == '(')
                {
                    break;
                }
                Pop(&s, &top);
                out[i++] = top;
            }
            Push(&s, *p);
            break;
        case '*':
        case '/':
            while (StackSize(&s) > 0)
            {
                GetTop(&s, &top);
                if (top == '+' || top == '-')
                {
                    Push(&s, *p);
                    break;
                } else {
                    Pop(&s, &top);
                    out[i++] = top;
                }
                
            }
            break;
        case '(':
            Push(&s, *p);
            break;
        case ')':
            do
            {
                pop_result = Pop(&s, &top);
                if (pop_result != OK)
                {
                    printf("格式错误！！");
                    exit(1);
                }
                if (top != '(')
                {
                    out[i++] = top;    
                }
            } while (top != '(');
            break;      
        default:
            out[i++] = *p;
            out[i++] = ' ';
            break;
        }
        p++;
    }
    while (Pop(&s, &top) == OK) 
    {
        out[i++] = top;
    }
    out[i] = 0;
    
    printf("the postfix expression is %s\n", out);

    return 0;
    
}
